package editor.cn;

import java.util.*;

class Solution56 {
    public static void main(String[] args) {
        Solution solution = new Solution56().new Solution();
        int[][] nums=new int[][]{{1,3},{2,6}};
        System.out.println(Arrays.toString(solution.merge(nums)));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {
            //    显然差分数组,还真搞不了。因为这个可以有相同的，只能按照左边界排序贪心来做。(注意按照多元素排序！！比较A，相同在比较B，相同在比较C)
            //    先找出最大的边界吧
            Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
            int maxEnd = intervals[intervals.length - 1][1];
            int[] diff = new int[maxEnd + 3];
            for (int[] interval : intervals) {
                diff[interval[0] + 1]++;//在差分数组最左边自动加一个0
                diff[interval[1] + 1]--;
            }
            LinkedList<List<Integer>> res = new LinkedList<>();//接受所有范围的结果
            LinkedList<Integer> path = new LinkedList<>();//接受范围的列表

            for (int i = 1; i < maxEnd + 3; i++) {
                diff[i]+=diff[i-1];
            }

            for (int i = 1; i < maxEnd + 3; i++) {
                if (diff[i - 1] == 0 && diff[i] != 0) {//寻找左边界
                    path.add(i-1);
                }

                if (diff[i - 1] != 0 && diff[i] == 0) {//寻找右边界
                    path.add(i-1);

                    res.add(new LinkedList<>(path));
                    path.removeLast();
                    path.removeLast();
                }
            }
            return res.stream()
                    .map(innerList -> innerList.stream().mapToInt(Integer::intValue).toArray())
                    .toArray(int[][]::new);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}












